package org.example.SolutionNew005;

import java.util.ArrayList;
import java.util.List;

public class Backtrack004 {
    public static void main(String[] args) {
        Backtrack004 b = new Backtrack004();
        System.out.println(b.generateParenthesis(3).toString());
    }

    List<String> res;
    //也是一个回溯，在回溯左括号的同时，保证右括号不超过左括号的个数
    public List<String> generateParenthesis1(int n) {
        res = new ArrayList<>();
        StringBuilder sb=new StringBuilder();
        sb.append("(");
        addAllList(n,1,0,sb);
        return res;
    }

    public void addAllList(int n, int left, int right,StringBuilder sb) {
        if(left==n&&right==n) res.add(sb.toString());

        if(left<n){
            sb.append("(");
            addAllList(n,left+1,right,sb);
            sb.deleteCharAt(sb.length()-1);
        }
        if(right<left){
            sb.append(")");
            addAllList(n,left,right+1,sb);
            sb.deleteCharAt(sb.length()-1);
        }
    }

    List<String>[] cache=new ArrayList[10];
    public List<String> generateParenthesis(int n) {
        return generate(n);
    }

    public List<String> generate(int n) {
        if(cache[n]!=null) return cache[n];
        List<String> list = new ArrayList<>();
        if(n==0){
            list.add("");
        }else{
            for(int i=0;i<n;i++){
                for(String left:generate(i)){
                    for(String right: generate(n-1-i)){
                        list.add("("+left+")"+right);
                    }
                }
            }
        }
        cache[n]=list;
        return list;
    }
}
